John Watrous 《Introduction to the Theory of Computing》16 -- 通用图灵机和不可判定语言

前言

这节课我们会讲到通用图灵机。这是一个确定性图灵机，当我们已知一个任意DTM编码时，它能够根据一个已知输入来模拟这个DTM。
　　为了描述这样一个通用机器，我们自然而然会想到DTM的编码，这也是我们本节课要做的第一件事。这个DTM编码方案的概念让我们首次见到了非半可判定（因此也就是不可判定）语言的例子。通过这个语言的非半可判定性，就能证明许多其他的语言是不可判定或者非半可判定的。我们先来看两个简单的例子，后面还会有更多。

知识点

DTM的编码方案

在上节课中我们详细讨论过DFA的编码方案，并且我们发现通过这个方案也能设计出NFA的编码方案。尽管我们没有具体讨论正则表达式和上下文无关语法的编码方案，我们只是说你们可以轻松设计出这些模型的编码方案。
　　对于DTM我们的计划也是一样的，因为相较于刚才所提的其他模型，这个模型并没有什么新的概念难点。然而，考虑到编码DTM语言在后续课程中的重要性，我们有必要小心谨慎地花点时间在这个编码上。正如我们在每个编码方案中所想到的，在DTM的编码中有很多可供选择的地方需要我们决定 — 我们最关心的还是这个编码方案细节要清晰明确，而且并不是因为细节本身就是可计算性学习的本质。
　　纵观接下来的讨论，我们将会假设

$$M=(Q,\Sigma,\Gamma,\delta,q_0,q_{acc},q_{rej})\tag{16.1}$$

是一个用来进行编码的已知DTM。我们假设$M$的状态集合$Q$的形式为

$$Q=\{q_0,...,q_{m-1}\},\tag{16.2}$$

其中$m$是一个正整数，$M$的输入和磁带字母表形式为

$$\Sigma=\{0,...,k-1\}\ \ \ \ 和\ \ \ \ \Gamma=\{0,...,n-1\},\tag{16.3}$$

其中$k$和$n$都是正整数。已知$\Sigma$是$\Gamma$的整自己，那么$k<n$；假设空格符号$\sqcup\in\Gamma$是$\Gamma$的最后一个符号$n-1$。
　　首先，一个状态$q\in Q$的编码应该被理解为用它的索引作为编码对象的二进制编码字符串$\langle q\rangle\in\{0,1\}^{*}$，所以

$$\langle q_0\rangle=0,\ \ \ \ \langle q_1\rangle=1,\ \ \ \ \langle q_2\rangle=10,\ \ \ \ etc.\tag{16.4}$$

磁带符号的编码方式类似，所以

$$\langle 0\rangle=0,\ \ \ \ \langle 1\rangle=1,\ \ \ \ \langle 2\rangle=10,\ \ \ \ etc.\tag{16.5}$$

我们可以把左右方向符号编码为

$$\langle \leftarrow\rangle=0\ \ \ \ 和\ \ \ \ \langle \rightarrow\rangle=1.\tag{16.6}$$

　　接下来我们需要一种方式编码转移函数$\delta$，它和我们上节课中DFA编码方式类似。对于状态$q\in Q\setminus \{q_{acc},q_{rej}\}$和$r\in Q$和磁带符号$a、b\in\Gamma$，以及方向$D\in\{\leftarrow,\rightarrow\}$，编码

$$\langle\langle q\rangle,\langle a\rangle,\langle r\rangle,\langle b\rangle,\langle D\rangle\rangle\in\{0,1\}^{*}\tag{16.7}$$

代表着

$$\delta(q,a)=(r,b,D).\tag{16.8}$$

转移函数$\delta$的编码通过按照字典顺序将每一对$(q,a)\in Q\setminus\{q_{acc},q_{rej}\}\times\Gamma$使用以上方法得到的二进制串列举出来即可获得。
　　最后，通过这些编码手段，我们从每个DTM $M$得到二进制字符串编码$\langle M\rangle\in\{0,1\}^{*}$如下：

$$\langle M\rangle=\langle\langle m\rangle,\langle k\rangle,\langle n\rangle,\langle \delta\rangle,\langle q_{acc}\rangle,\langle q_{rej}\rangle\rangle.\tag{16.9}$$

案例16.1. 回想我们图12.3中的语言$SAME$的DTM $M$，我们有

$$\begin{align}\delta(q_0,0)&=(q_0,0,\leftarrow), \\ \delta(q_0,1)&=(q_0,1,\leftarrow), \\ \delta(q_0,\sqcup)&=(q_1,\sqcup,\rightarrow), \\ &\vdots \\\delta(q_3,0)&=(q_{rej},0,\leftarrow), \\ \delta(q_3,1)&=(q_0,\sqcup,\leftarrow), \\ \delta(q_3,\sqcup)&=(q_{rej},\sqcup,\leftarrow).\end{align}\tag{16.10}$$

我需要说明一下$q_{acc}=q_r$和$q_{rej}=q_5$，我们还明确知道有$m=6$个状态，$k=2$个输入符号，以及$n=3$个磁带符号，也就是空格符号$\sqcup$，它是最后一个磁带符号 $2$。
　　转移$\delta(q_0,0)=(q_0,0,\leftarrow)$的编码是

$$\langle\langle q_0\rangle,\langle 0\rangle,\langle q_0\rangle,\langle 0\rangle,\langle \leftarrow\rangle\rangle=\langle 0,0,0,0,0\rangle,\tag{16.11}$$

转移$\delta(q_0,1)=(q_0,1,\leftarrow)$的编码是

$$\langle\langle q_0\rangle,\langle 1\rangle,\langle q_0\rangle,\langle 1\rangle,\langle \leftarrow\rangle\rangle=\langle 0,1,0,1,0\rangle,\tag{16.12}$$

然后跳到最后一个，转移$\delta(q_3,2)=(q_5,2,\leftarrow)$的编码是

$$\begin{align}\langle\langle &q_3\rangle,\langle \sqcup\rangle,\langle q_{rej}\rangle,\langle \sqcup\rangle,\langle \leftarrow\rangle\rangle \\ &= \langle\langle q_3\rangle,\langle 2\rangle,\langle q_5\rangle,\langle 2\rangle,\langle \leftarrow\rangle\rangle =\langle 11,10,101,10,0\rangle.\end{align}\tag{16.13}$$

完整的转移函数$\delta$的编码是

$$\begin{align}\langle\delta\rangle &=\langle\langle\langle q_0\rangle,\langle 0\rangle,\langle q_0\rangle,\langle 0\rangle,\langle \leftarrow\rangle\rangle,\langle\langle q_0\rangle,\langle 1\rangle,\langle q_0\rangle,\langle 1\rangle,\langle \leftarrow\rangle\rangle, \\ ...,\langle\langle &q_3\rangle,\langle \sqcup\rangle,\langle q_{rej}\rangle,\langle \sqcup\rangle,\langle \leftarrow\rangle\rangle\rangle \\ &=\langle\langle 0,0,0,0,0\rangle,\langle 0,1,0,1,0\rangle,\langle 11,10,101,10,0\rangle\rangle.\end{align}\tag{16.14}$$

到了最后$M$的编码就是

$$\langle M\rangle=\langle\langle 6\rangle,\langle 2\rangle,\langle 3\rangle,\langle\delta\rangle,\langle 0\rangle,\langle 4\rangle,\langle 5\rangle\rangle.\tag{16.15}$$

通用图灵机

现在我们定义一个DTM的编码方案，我们能模拟在一个已知DTM中执行一个已知输入的计算任务了。通用图灵机就是能执行这样的模拟的一个DTM — 之所以称它通用是因为它有模拟所有其他DMT的能力。
　　回想我们第12节课中DTM的配置

$$M=(Q,\Sigma,\Gamma,\delta,q_0,q_{acc},q_{rej})\tag{16.16}$$

可以表达成这种形式

$$u(q,a)v,\tag{16.17}$$

其中状态$q\in Q$，磁带符号$a\in\Gamma$，磁带符号字符串$u、v\in\Gamma^{*}$，而且$u$不以空格符号开头，$v$不以空格符号结尾。这样一个配置可以编码为

$$\langle u(q,a)v\rangle=\langle\langle u\rangle,\langle\langle q\rangle,\langle a\rangle\rangle,\langle v\rangle\rangle,\tag{16.18}$$

这里$\langle u\rangle、\langle q\rangle、\langle a\rangle$和$\langle v\rangle$指代合适的编码方案，这个我们在本节课已经讨论过了。
　　现在，如果你想要的模拟在一个已知DTM $M$中输入字符串$w$的计算，一个很自然的方式就是记录$M$的配置，并且适时地进行更新，就像计算本身那样要求的。具体一点，我们将从$M$的初始配置开始输入$w$，也就是

$$(q_0,\sqcup)w.\tag{16.19}$$

然后我们重复地计算$M$下一个配置，反复进行，知道我们得到某个配置，它的状态是$q_{acc}$或者$q_{rej}$，如此我们才可以停止。我们也许永远得不到这样一个配置；如果$M$永远在输入$w$上执行下去，我们的模拟也会永远进行。不难看出，这是不可避免的。
　　有了这样一个办法，让我们来重点关注决定下一个配置的任务，也就是每个计算步骤得到的结果，对于一个已知DTM $M$和$M$的一个已知配置。我们来看看这个函数的定义

$$next:\{0,1\}^{*}\rightarrow\{0,1\}^{*}.\tag{16.20}$$

对于每个DTM$ M=(Q,\Sigma,\Gamma,\delta,q_0,q_{acc},q_{rej})$和$M$的非停止配置$u(q,a)v$，我们定义

$$next(\langle\langle M\rangle,\langle u(q,a)v\rangle\rangle)=\langle x(p,b)y\rangle,\tag{16.21}$$

其中$x(p,b)y$是$M$处于配置$u(q,a)u$时运行一步得到的配置，也就是

$$u(q,a)v\vdash_M x(p,b)y\tag{16.22}$$

的唯一配置。我们可以回忆一下12.2定义的精确术语。对于每个$M$停止配置$u(q,a)v$，让我们定义（方便起见）

$$next(\langle\langle M\rangle,\langle u(q,a)v\rangle\rangle) =\langle u(q,a)v\rangle.\tag{16.23}$$

如果输入$x\in\{0,1\}^{*}$的形式不是$\langle\langle M\rangle,\langle u(q,a)v\rangle\rangle$，按要求$M$是一个DTM，$u(q,a)v$是一个配置，我们应该返回$next(x)=\varepsilon$。
　　让我们想想这个函数如何用堆栈机来计算。自然而然第一步应该是处理输入，基于这个过程结束后，我们有一个栈$\sf{M}$存储$\langle M\rangle$，还有四个栈$\sf{S}、\sf{T}、\sf{L}$和$\sf{R}$，它们初始化后分别存储着编码$\langle q\rangle、\langle a\rangle、\langle u\rangle$和$\langle v\rangle$。在这个处理中，如果遇到不是我们期望的编码就停止然后输出$\epsilon$。
　　接下来，编码$\langle M\rangle$中的编码$\langle \delta\rangle$存储的转移函数，它可以用来检测决定$\delta(q,a)=(p,b,D)$。这需要扫描一次$\langle\delta\rangle$来获得，在找到一个包含$\sf{S}$和$\sf{T}$中存储的字符串$\langle q\rangle$和$\langle a\rangle$，以及编码$\langle p\rangle、\langle b\rangle$和$\langle D\rangle$的匹配后。这些编码会被存进相应地栈中，我们就不再点名了。$\sf{S}、\sf{T}、\sf{L}$和$\sf{R}$的操作就是更新它们的内容$\langle p\rangle、\langle b\rangle、\langle x\rangle$和$\langle y\rangle$，其中$p、b、x$和$y$要满足(16.22)，才会执行更新。
　　最后，这些字符串连起来就是输出字符串

$$\langle\langle x\rangle,\langle\langle p\rangle,\langle b\rangle\rangle,\langle y\rangle\rangle.\tag{16.24}$$

用这种方式详细说明一个DSM的运作是个耗时过程，但是在概念水平上，这个计算就能合理地简洁说明。字符串匹配的子程序当然会很有帮助。
　　有$next$函数在手，你们就可以用上述方式模拟在已知DTM $M$上输入已知的$w$了，通过从将$M$初始化配置设置为$(q_0,\sqcup)w$，然后重复执行$next$函数即可。
　　现在考虑下面这个语言，它类似于我们上节课讨论的关于$A_{DFA}、A_{NFA}、A_{REG}$和$A_{CFG}$的语言：

$$A_{DTM}=\{\langle\langle M\rangle,\langle w\rangle\rangle: M是一个DTM并且w\in L(M)\}.\tag{16.25}$$

我们得出$A_{DTM}$是半可判定的：图16.1中的DSM $\mathfrak{U}$使得$L(\mathfrak{U})=A_{DTM}$。这个DSM命名为$\mathfrak{U}$的原因是为了表示它是一个通用（universal）DSM。就像我们第14节课中讲的，DSM $\mathfrak{U}$可以被一个DTM模拟。

命题16.2. 语言$A_{DTM}$是半可判定的。

　　在我们进入下一小节之前，让我们注意一下下面这个可判定语言：

$$S_{DTM}=\left\{\langle\langle M\rangle,\langle w\rangle,\langle t\rangle\rangle:\begin{align}&M是一个DTM，w是M的一个输入，\\ &t\in\mathbb{N}，并且M能接t步之内接受w\end{align}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \right\}.\tag{16.26}$$

这个语言能够由按照前面描述的基本相同的模拟来判定，但是如果$M$在输入$w$的$t$步之后还没停止，那么模拟就会中断然后拒绝。

一些不可判定语言

到了现在自然大家都会问到：$A_{DTM}$是不是可判定的，现在已知它是半可判定的。我们将会证明答案是不可判定的。然而在此之前，我们将会先看一看另外一个语言，它甚至都不是半可判定的。这个语言是

$$DIAG=\{\langle M\rangle:M是一个DTM并且\langle M\rangle\notin L(M)\}.\tag{16.27}$$

也就是语言$DIAG$包含了所有遵守了我们本节课开头讲的编码规则的二进制字符串$M$，但是DTM $M$不能接受它自身的编码。注意如果字符串$\langle M\rangle$编码是一个输入字母表只有一个字符的DTM，也就是不包含0和1，那么确实$\langle M\rangle\notin L(M)$。

定理16.3. 语言$DIAG$是非半可判定的。

证明：通过反证法，假设语言$DIAG$是半可判定的。那么一定存在一个DTM $M$s使得$L(M)=DIAG$。
　　现在，考虑$M$的编码$\langle M\rangle$。由语言$DIAG$的定义可知

$$\langle M\rangle\in DIAG \Leftrightarrow \langle M\rangle\notin L(M).\tag{16.28}$$

另外，因为$M$能够识别$DIAG$，那么

$$\langle M\rangle\in DIAG\Leftrightarrow \langle M\rangle\in L(M).\tag{16.29}$$

结果是

$$\langle M\rangle\notin L(M)\Leftrightarrow \langle M\rangle\in L(M),\tag{16.30}$$

这是矛盾的，我们得出$DIAG$是非半可判定的。

备注16.4. 注意这个证明和我们第一节课将的$\mathcal{P}(\mathbb{N})$是不可数的证明类似。$DIAG$的非半可判定性质是非常简单；几乎没有用到我们定义的具体DTM模型或者编码方案。

　　现在我们知道$DIAG$是非半可判定的，我们将会证明$A_{DTM}$是不可判定的。

定理16.5. 语言$A_{DTM}$是不可判定的。

证明：通过反证法，假设$A_{DTM}$是可判定的。因此一定存在一个DTM $T$能够判定$A_{DTM}$。定义一个新的DTM $K$如图16.2所示。

　　对于已知的DTM $M$，我们也许想问对于输入$\langle M\rangle$，$K$的作用是什么。如果$\langle M\rangle\in DIAG$，那么根据定义$\langle M\rangle\notin L(M)$，因此$\langle\langle M\rangle,\langle M\rangle\rangle\notin A_{DTM}$（因为$M$不接受$\langle M\rangle$）。这说明$T$拒绝了输入$\langle\langle M\rangle,\langle M\rangle\rangle$，因此$K$一定接受输入$\langle M\rangle$。如果情况相反，$\langle M\rangle\notin DIAG$，那么$\langle M\rangle\in L(M)$，因此$\langle\langle M\rangle,\langle M\rangle\rangle \in A_{DTM}$。这说明$T$接受输入$\langle\langle M\rangle,\langle M\rangle\rangle$，因此$K$一定拒绝输入$\langle M\rangle$。最后一种可能性就是$K$的输入根本不是一个DTM编码，这种情况它直接拒绝。
　　考虑了所有的可能性，我们发现$K$判定了语言$DIAG$。然而这与实际情况矛盾，$DIAG$是非半可判定的（因此也是不可判定的）。有了这个矛盾，我们得出$A_{DTM}$是不可判定的。

　　这里有另外一个例子，它是$A_{DTM}$的一个著名的亲戚。

$$HALT=\{\langle\langle M\rangle,\langle w\rangle\rangle:M是一个DTM，并且输入w一定会停止\}.\tag{16.31}$$

这里的停止意味着$M$输入$w$后一定会接受或者拒绝。让我们先达成一个共识，“$M$输入$w$一定会停止”在某种情况下不成立，如果$w$包含了不属于$M$输入字母表的字符 — 纯粹是一个术语上的问题。
　　很容易可以证明$HALT$是半可判定的，我们只需要运行一个改版的通用图灵机$\mathfrak{U}$输入$\langle\langle M\rangle,\langle w\rangle\rangle$，除了我们接受的情况模拟结果是接受或者拒绝外 — 当出现$M$输入$w$不停止的情况，这个改版的$\mathfrak{U}$将会永远运行在输入$\langle\langle M\rangle,\langle w\rangle\rangle$上。

定理16.6. 语言$HALT$是不可判定的。

证明：通过反证法，假设$HALT$是可判定的，所以一定存在一个$DTM$能够判定它，定义一个新的DTM $K$如图16.3所示。DTM $K$能够判定$A_{DTM}$，来看下面的情况分析

1. 如果$M$接受$w$，那么$T$就会接受$\langle\langle M\rangle,\langle w\rangle\rangle$（因为$M$输入$w$停止了），这个$M$输入$w$的模拟结果就是接受。
2. 如果$M$拒绝$w$，那么$T$就会拒绝$\langle\langle M\rangle,\langle w\rangle\rangle$（因为$M$输入$w$停止了），这个$M$输入$w$的模拟结果就是拒绝。
3. 如果$M$输入$w$一直运行，那么$T$就会拒绝$\langle\langle M\rangle,\langle w\rangle\rangle$，因此$K$在模拟$M$输入$w$之前就会拒绝。

然而这是矛盾的，因为$A_{DTM}$是不可判定的。有了这个矛盾，我们得出$HALT$是不可判定的。

原文链接

https://cs.uwaterloo.ca/~watrous/ToC-notes/ToC-notes.16.pdf